Papers with space complexity
A Formal Hierarchy of RNN Architectures (2020.acl-main)
Copied to clipboard
| Challenge: | Existing theories of expressive power of RNNs are limited. |
| Approach: | They propose a formal hierarchy of the expressive capacity of RNN architectures based on two formal properties: space complexity and rational recurrence. |
| Outcome: | The proposed model is based on the theory of “saturated” RNNs and shows that it obeys a similar hierarchy to unsaturated RNN models. |
LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning (2024.findings-emnlp)
Copied to clipboard
| Challenge: | Existing path planning algorithms suffer from significant computational and memory inefficiencies as the state space grows . large language models excel in environmental analysis but fall short in detailed spatial and temporal reasoning . |
| Approach: | They propose a new path planning method that synergistically combines A* and LLMs to improve pathfinding efficiency. |
| Outcome: | The proposed method improves pathfinding efficiency while maintaining integrity of path validity in large-scale scenarios. |
Sub-Sentence Encoder: Contrastive Learning of Propositional Semantic Representations (2024.naacl-long)
Copied to clipboard
Sihao Chen, Hongming Zhang, Tong Chen, Ben Zhou, Wenhao Yu, Dian Yu, Baolin Peng, Hongwei Wang, Dan Roth, Dong Yu
| Challenge: | Sentence embeddings are typically learned to recognize the semantic relation between two text inputs. |
| Approach: | They introduce a contrastively-learned contextual embedding model for fine-grained semantic representation of text. |
| Outcome: | The proposed model is able to produce contextual embeddings corresponding to different atomic propositions, i.e. semantic equivalence between propositions across different text sequences. |
Strong Baselines for Neural Semi-Supervised Learning under Domain Shift (P18-1)
Copied to clipboard
| Challenge: | Existing neural models for learning under domain shifts only evaluate on a single task, on proprietary datasets, or compare to weak baselines. |
| Approach: | They propose a multi-task tri-training method that reduces time and space complexity of classic bootstrapping approaches. |
| Outcome: | The proposed method outperforms the state-of-the-art for sentiment analysis on two benchmarks. |
Hexatagging: Projective Dependency Parsing as Tagging (2023.acl-short)
Copied to clipboard
| Challenge: | Using a pretrained language model, we can train language models on increasingly large amounts of data. |
| Approach: | They propose a dependency parser that constructs dependency trees by tagging words with elements from a finite set of possible tags. |
| Outcome: | The proposed approach achieves state-of-the-art performance of 96.4 LAS and 97.4 UAS on the Penn Treebank test set. |
Sequence Parallelism: Long Sequence Training from System Perspective (2023.acl-long)
Copied to clipboard
| Challenge: | Existing work on memory-efficient parallelisms to reduce time and space complexity focuses on reducing time and complexity from system perspective. |
| Approach: | They propose a memory-efficient parallelism to reduce time and space complexity . they split input sequence into multiple chunks and feed each chunk into GPU . |
| Outcome: | The proposed approach is compatible with most existing parallelisms and makes 4D parallelismal possible. |
Sharper and Faster mean Better: Towards More Efficient Vision-Language Model for Hour-scale Long Video Understanding (2025.acl-long)
Copied to clipboard
| Challenge: | Existing multimodal large language models (LLMs) have shown impressive performance on the video understanding task, but extremely long videos still pose significant challenges to their context length, memory consumption, and computational complexity. |
| Approach: | They propose a vision-language model named Sophia for long video understanding which can efficiently handle hour-scale long videos. |
| Outcome: | The proposed model exhibits competitive performance compared to existing video understanding baselines across various benchmarks for long video understanding with reduced time and memory consumption. |
The NLP Task Effectiveness of Long-Range Transformers (2023.eacl-main)
Copied to clipboard
| Challenge: | Existing benchmarks on long-range attention models have not been sufficient to develop efficient Transformers and their practical application on complex NLP tasks. |
| Approach: | They propose to benchmark 7 Transformer variants on 5 difficult NLP tasks and 7 datasets to examine their capacity for long-range attention. |
| Outcome: | The proposed models have advantages on content selection and query-guided decoding, but they come with previously unrecognized drawbacks such as insufficient attention to distant tokens and accumulated approximation error. |
Recurrent Neural Language Models as Probabilistic Finite-state Automata (2023.emnlp-main)
Copied to clipboard
| Challenge: | Existing studies have focused on the expressive power of recurrent neural network LMs to recognize unweighted formal languages. |
| Approach: | They propose to model a strict subset of probabilistic finite-state automata with RNNs . they show that an RNN requires left(N ||right) neurons to represent an LM . |
| Outcome: | The proposed language models can represent a strict subset of probabilistic distributions expressed by finite-state models. |
Fourier Transformer: Fast Long Range Modeling by Removing Sequence Redundancy with FFT Operator (2023.findings-acl)
Copied to clipboard
| Challenge: | Existing transformer models are computationally demanding and prohibitively costly for long sequences due to the quadratic complexity of its selfattention module. |
| Approach: | They propose a transformer-based model that inherits weights from large pretrained models by removing redundancies in hidden sequences using the ready-made Fast Fourier Transform operator. |
| Outcome: | The proposed model outperforms the standard BART model on the long-range modeling benchmark LRA with significant improvements in speed and space. |
Text Anomaly Detection with Simplified Isolation Kernel (2025.findings-emnlp)
Copied to clipboard
| Challenge: | High-dimensional dense embeddings extracted by large language models pose memory requirements and high computation time. |
| Approach: | They propose a method that maps high-dimensional dense embeddings to lower-dimensional sparse representations while preserving crucial anomaly characteristics. |
| Outcome: | The proposed method achieves better detection performance than 11 SOTA anomaly detection algorithms while maintaining computational efficiency and low memory cost. |
Exploring Space Efficiency in a Tree-based Linear Model for Extreme Multi-label Classification (2024.emnlp-main)
Copied to clipboard
| Challenge: | Extreme multi-label classification (XMC) aims to identify relevant subsets from numerous labels. |
| Approach: | They propose to store a tree model under the assumption of sparse data under the condition that some features may be unused when training binary classifiers in a trees method. |
| Outcome: | The proposed method can save 10% of the size of the standard one-vs-rest method for multi-label classification. |